package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Problem146C {

	/**
	 * 满足条件的n需要满足下面条件：
	 * n = 0 	 (mod 2)
	 * n = -1, 1 (mod 3)
	 * n = 0 	 (mod 5)
	 * n = -3, 3 (mod 7)
	 * ...
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		
		long MAX = 1000000;
		int[] primes = new int[] {2,3,5,7,11,13,17};
		int mul = 1;
		for (int i = 0; i < primes.length; i ++) mul *= primes[i];
		int[] ms = new int[] {1, 3, 7, 9, 13, 27};	//n^2 + ms[i]是素数
		int[] ns = new int[] {19, 21};	//n^2 + ns[i]不能是素数
		int[] rs = remains(ms, primes);
		
		long s = 0;
		for (long n = 1; n < MAX; n ++) {
			int r = (int)(n%mul);
			if (Arrays.binarySearch(rs, r) >= 0) {
				long n2 = n*n;
				boolean prime = true;
				for (int k = 0; k < ms.length; k ++) {
					if (!BigInteger.valueOf(n2+ms[k]).isProbablePrime(64)) {
						prime = false;
						break;
					}
				}
				if (prime) {
					boolean notPrime = true;
					for (int k = 0; k < ns.length; k ++) {
						if (BigInteger.valueOf(n2+ns[k]).isProbablePrime(64)) {
							prime = false;
							break;
						}
					}
					if (notPrime) {
						System.out.println(n);
						s += n;
					}
				}
			}
		}
		System.out.println("s(" + MAX + ") = " + s);
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}
	
	private static int[] remains(int[] ms, int[] primes) {
		
		int max = 1;
		for (int i = 0; i < primes.length; i ++) max *= primes[i];
		
		List<Integer> rs = new ArrayList<Integer>();
		for (int n = 0; n < max; n ++) {
			long i2 = ((long)n)*n;
			boolean ok = true;
			for (int i = 0; i < primes.length; i ++) {
				for (int j = 0; j < ms.length; j ++) {
					if ((i2 + ms[j]) % primes[i] == 0) {
						ok = false;
						break;
					}
				}
				if (!ok) break;
			}
			if (ok) rs.add(n);
		}
		
		int[] ret = new int[rs.size()];
		for (int i = 0; i < rs.size(); i ++) ret[i] = rs.get(i);
		return ret;
	}
}
